⟸ Go Back ⟸

Exercise 9 (Homework 2).

(regular languages, NFAs vs DFAs, pigeonhole principle, minimization of DFAs)

NFAs can be exponentially more succinct than DFAs

Given an n\in \mathbb N, consider the language L_n = \{ xay \mid x,y \in \{a,b\}^* \land |y| = n\}.

1. What is the cost of the determinization algorithm (as a function of the size of the input NFA)?

2. Show that L_n is regular by constructing an NFA recognizing L_n and having n+2 states.

3. Show that the minimum DFA recognizing L_n has 2^{n+1} states. In other words,

   1. show that there is a DFA recognizing L_n having 2^{n+1} states and
   2. show that no DFA with strictly less than 2^{n+1} states can recognize L_n.

Remember that the compact notation used in the definition of L_n corresponds to the language \{ w \in \{a,b\}^* \mid \exists x,y\ (w=xay \land |y| = n)\}.